package hot100.滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * @ https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
 * @date 2025/08/24
 */
public class 找到字符串中所有字母异位词_438 {

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(1);
        list.add(1);

    }

    /**
     * 滑动窗口
     * 子串必须是p的长度
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        int[] cnt = new int[26];
        int[] pArr = new int[26];
        for (char c : p.toCharArray()) {
            pArr[c - 'a']++;
        }

        int right = 0;
        for (int left = 0; left < s.length(); left++) {

            while (right < s.length() && right - left + 1 <= p.length()) {
                cnt[s.charAt(right) - 'a']++;
                right++;
            }
            if (isAnagrams(cnt, pArr)) {
                list.add(left);
            }

            cnt[s.charAt(left) - 'a']--;
        }

        return list;
    }

    private boolean isAnagrams(int[] cnt, int[] pArr) {
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] != pArr[i]) {
                return false;
            }
        }
        return true;
    }

}
